home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / node_set.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  1.7 KB  |  60 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.9 Sets of nodes and edges (node\_set, edge\_set)}
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $S$ of the data type $node\_set$ ($edge\_set$) is a subset of 
  8. the nodes (edges) of a graph $G$. $S$ is said to be valid for the nodes 
  9. (edges) of $G$.
  10.  
  11.  
  12. \bigskip
  13. {\bf 2. Creation}
  14.  
  15. $node\_set$ $S(G)$;\nl
  16. $edge\_set$ $S(G)$;
  17.  
  18. creates an instance $S$ of type $node\_set$  ($edge\_set$) valid for all nodes
  19. (edges) currently contained in graph $G$ and initializes it to the empty set. 
  20.  
  21.  
  22. \bigskip
  23. \def\var{$S$}
  24. {\bf 3. Operations on a node/edge set S}
  25. \medskip
  26. \+\op void insert {x}                 
  27.                                 {adds node (edge) $x$ to $S$}
  28. \smallskip
  29. \+\op void del {x}                    
  30.                                 {removes node (edge) $x$ from $S$}
  31. \smallskip
  32. \+\op bool member {x}                 
  33.                                 {returns true if $x$ in $S$, false otherwise}
  34. \smallskip
  35. \+\op node/edge choose {}                 
  36.                                 {return a node (edge) of $S$}
  37. \smallskip
  38. \+\op int  size  {}                  
  39.                                 {returns the size of $S$}
  40. \smallskip
  41. \+\op bool  empty {}                  
  42.                                 {returns true iff $S$ is the empty set}
  43. \smallskip
  44. \+\op void clear {}                   
  45.                                 {makes $S$ the empty set}
  46.  
  47. \bigskip
  48. {\bf 4. Implementation}
  49.  
  50. A node (edge) set $S$ for a graph $G$ is implemented by a combination of a 
  51. list  $L$ of nodes (edges) and a node (edge) array of list\_items 
  52. associating with each node (edge) its position in $L$. All operations 
  53. take constant time, except of clear which takes time $O(|S|)$. The space 
  54. requirement is $O(n)$, where $n$ is the number of nodes (edges) of $G$.
  55.  
  56.  
  57. \vfill\eject
  58.  
  59.  
  60.